home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / compression / xpk / xpkhfmn.lha / HFMN.doc < prev    next >
Encoding:
Text File  |  1993-11-01  |  4.3 KB  |  117 lines
  1.  
  2.                                       HFMN
  3.               A very fast packing & fast unpacking dynamic huffman
  4.                                   Version 1.16
  5.                           Copyright 1993 Martin Hauner
  6.  
  7.  
  8.  
  9.                                License/Disclaimer
  10.                                ------------------
  11.  
  12. This library may be freely distributed with the XPK compression package, as long
  13. as  it  is  kept  in its original, complete, and unmodified form.  It may not be
  14. distributed  by  itself  or  in  a  commercial  package  of  any kind without my
  15. permission.
  16.  
  17. This  program is distributed in the hope that it will be useful, but WITHOUT ANY
  18. WARRANTY;  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  19. PARTICULAR PURPOSE.
  20.  
  21.  
  22.                                   Description
  23.                                   -----------
  24.  
  25. This  XPK  sub-library  basically  uses  the same algorithm (dynamic huffman) as
  26. found  in  the xpkHUFF.library.  For more detailed information about the huffman
  27. algorithm, take a look into HUFF.doc from M.Zimmermann -- and skip the part that
  28. huffman  compression  &  decompression is pretty slow !.  In difference to HUFF,
  29. HFMN  is  FAST  on  compression and decompression and produces a slightly better
  30. output.   Although  the  basic  algorithm  is the same, it is entirely different
  31. implemented, therefore HFMN will not depack HUFF and HUFF not HFMN !
  32.  
  33.  
  34.  
  35.      Actually  HFMN is, with 68000 code and Amiga 4000/40, ..... than HUFF.
  36.  
  37.                · ~2.3 times faster on ascii file compression
  38.                · ~3.5 times faster on executeable file compression
  39.                · ~1.5 times faster on decompression
  40.                · ~350 byte shorter per 65535 Byte (MaxPkInChunk)
  41.  
  42.      HFMN needs for private buffers (no xpkmaster.library buffers) 
  43.  
  44.                ·  7.5 Kbyte packing memory
  45.                ·  6   KByte unpacking memory
  46.  
  47.  
  48.  
  49. Following  is  a  table briefly listing some comparative statistics for HFMN and
  50. HUFF.   These  were  generated  by  xBench  on the standard XPK benchmark system
  51. (A3000/25  with  SCRAM,  using  the  AmigaVision  executeable  as  data)  and on
  52. A4000/40.  Note that memory needs don't include xpkmaster.library's buffers.
  53.  
  54.  
  55.         Method   Packing   Unpacking   Packing   Unpacking   Compression
  56.                  Memory     Memory      Speed      Speed        Ratio
  57.         ------   -------   ---------   -------   ---------   -----------
  58.          HFMN      7.5 K      6 K      224 K/s    194 K/s        24.7
  59.  
  60.          HUFF     30   K     71 K ?     88 K/s    138 K/s        24.1
  61.  
  62.  
  63.                          and now the same with A4000/40
  64.  
  65.  
  66.         Method   Packing   Unpacking   Packing   Unpacking   Compression
  67.                  Memory     Memory      Speed      Speed        Ratio
  68.         ------   -------   ---------   -------   ---------   -----------
  69.          HFMN      7.5K        6K      405 K/s    422 K/s        24.7
  70.  
  71.          HUFF     30K         71K ?    130 K/s    260 K/s        24.1
  72.  
  73.  
  74.  
  75. For what reasons is HFMN so different from HUFF ?
  76.  
  77.  ·  First,  i use heapsort to create the huffman tree, which is most responsible
  78.     for  packing speed.
  79.     (heapsort is the second-best sort algorithm and is based upon binary trees)
  80.  
  81.  ·  Second, i generate an (almost) optimal unpack code from the huffman tree. So
  82.     best possible unpacking speed is (nearly) reached.
  83.  
  84.  ·  Third,  i save the huffman tree recursivly.  Therefore i need max.  320 byte
  85.     to save the huffman tree and output size is slightly improved against HUFF.
  86.  
  87.  
  88.  
  89.                                      Thanks
  90.                                      ------
  91.  
  92.                               to Karsten Dageförde
  93.  
  94.                                       for
  95.                          · his help on my first packer
  96.         · telling  me some bit tricks, especially about using the x-flag
  97.  · producing ideas to improve HFMN (save tree recursivly, generate unpack code)
  98.  
  99.                                to Bilbo the first
  100.                                       for
  101.  
  102.                         · providing A3000 xBench ratings
  103.  
  104.  
  105.  
  106.                                 Version History
  107.                                 ---------------
  108.  
  109.                          V 1.16 - first public version.
  110.  
  111.  
  112.                                 Contact Address
  113.                                 ---------------
  114.  
  115.     Martin Hauner
  116.     sorry, no email
  117.